home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / challenge / 13.04 / 13.04 Challenge.sit / Challenge Column 13.04 / SortWindow.cpp < prev    next >
Text File  |  1997-01-21  |  3KB  |  132 lines
  1. /* SortWindow.cpp  
  2.    Charles Higgins 
  3. */
  4.    
  5. #include "SortWindow.h"
  6.  
  7. void swap(BWindow *aWindow, char **s1, char **s2);
  8. char **addlist( BWindow *aWindow, char **list, int numberOfThings);
  9.    
  10. SortWindow::SortWindow(BRect frame)
  11.                 : BWindow(frame, "Sort", B_TITLED_WINDOW, 0)
  12. {
  13.    BRect            aRect = frame;
  14.    BListView       *aView;
  15.    
  16.    aRect.OffsetTo(B_ORIGIN);
  17.    aView = new BListView(aRect, "SortView", B_FOLLOW_ALL, B_WILL_DRAW);
  18.    this->AddChild(aView);
  19. }
  20.  
  21. void swap(BWindow *aWindow, char **s1, char **s2)
  22. {
  23.    BView   *aView;
  24.    char    *temp;
  25.    
  26.    aView = aWindow->FindView("SortView");
  27.    aWindow->Lock();
  28.    temp = *s1;
  29.    *s1 = *s2;
  30.    *s2 = temp;
  31.    aView->Invalidate();
  32.    aWindow->Unlock();
  33. }
  34.  
  35. char **addlist( BWindow *aWindow, char **list, int numberOfThings)
  36. {
  37.    BListView       *aView;
  38.    int              i;
  39.    
  40.    aView = (BListView*)aWindow->FindView("SortView");
  41.    aWindow->Lock();
  42.    for(i=0;i< numberOfThings;i++)
  43.       aView->AddItem(list[i]);
  44.    aWindow->Unlock();
  45.    return((char**)aView->Items());
  46. }
  47.  
  48. void SortWindow::DoSort
  49.       ( char *thingsToSort[], int numberOfThings, SortType sortMethod)
  50. {
  51.    short            i,
  52.                     j,
  53.                     k,
  54.                     sorted = FALSE;
  55.    char           **myList;
  56.                    
  57.    myList = addlist( this, thingsToSort, numberOfThings);
  58.    switch(sortMethod)
  59.    {
  60.       case kBubbleSort:
  61.          i = numberOfThings-1;
  62.          while(i>0)
  63.          {
  64.             j=i;
  65.             for(k=0;k<i;++k)
  66.             {
  67.                if (0 < strcmp(myList[k],myList[j]))
  68.                   j = k;
  69.             }
  70.             swap( this, &myList[i], &myList[j]);
  71.             i--;
  72.          }
  73.          break;
  74.       case kExchange:
  75.          while(!sorted)
  76.          {
  77.             sorted = TRUE;
  78.             for(i=0;i<numberOfThings-1;i++)
  79.             {
  80.                if(0 < strcmp(myList[i],myList[i+1]))
  81.                {                  
  82.                   sorted = FALSE;
  83.                   swap( this, &myList[i], &myList[i+1]);
  84.                }
  85.             }
  86.          }
  87.          break;
  88.       case kMySort:
  89.          QuickSort( myList, 0, numberOfThings);
  90.          break;
  91.    }
  92.    memcpy(thingsToSort,myList,numberOfThings*sizeof(char*));
  93.    be_app->PostMessage(B_QUIT_REQUESTED);
  94. }
  95.  
  96. void SortWindow::QuickSort( char **list, int first, int last)
  97. {
  98.    int              j,i;
  99.  
  100.    while(last - first > 1)
  101.    {
  102.       i = first;
  103.       j = last;
  104.       for(;;)
  105.       {
  106.          while(++i < last && strcmp(list[i],list[first]) < 0)
  107.             ;
  108.          while(--j > first && strcmp(list[j],list[first]) > 0)
  109.             ;
  110.          if (i >= j)
  111.             break;
  112.          swap( this, &list[i], &list[j]);         
  113.       }
  114.       if( j == first)
  115.       {
  116.          ++first;
  117.          continue;
  118.       }
  119.       swap( this, &list[first], &list[j]);      
  120.       if(j - first < last - (j+1))
  121.       {
  122.          QuickSort( list,first,j);
  123.          first = j + 1;
  124.       }
  125.       else
  126.       {
  127.          QuickSort( list,j+1,last);
  128.          last = j;
  129.       }
  130.    }
  131. }
  132.